The present invention relates generally to scheduling of processing resources and, more particularly, to methods and apparatus for joint scheduling of multiple processes on a shared processor.
A typical communication network includes media gateways for processing of media streams representing voice, audio, and/or video. The media gateway is responsible for timely processing and delivery of the media stream to ensure a desired quality of service (QoS). One of the factors governing QoS in a communication network is end-to-end delay, i.e. how long it takes to deliver packets from the source to the destination. In general, it is desirable to keep the end-to-end delay as low as possible.
The end-to-end delay comprises several components, including algorithmic delay, processing delay, and queuing delay at the media gateway. Algorithmic delay and processing delay are a function of the particular coding algorithms and the processing platforms, which are typically fixed. By contrast, queuing delay depends on the time when data for a given communication channel is scheduled for processing, allowing a measure of control.
Control of queuing delay for a processor handling a single channel is relatively simple, as the schedule for the processing of the data has to be aligned to either the arrival phase of incoming data, or to a desired transmission phase. Some complication arises owing to the fact that interactive communication channels require independent (and concurrent) processing in two directions, giving rise to potential conflict between the requirements of the two transmission directions. The magnitude of the problem increases sharply when a processor is shared among many channels, as the likelihood of conflict in scheduling requirements increases with the number of channels sharing the same processor. The resolution of the problem requires a scheduling mechanism that can provide a practical trade-off in handling of the conflicting requirements of the two processing directions for many channels served by the processor, while ensuring that the calculation of the schedule itself can be done with a reasonable amount of processing for minimal overhead.
Scheduling algorithms for scheduling multiple processes on a shared processor are known. A process is a task which is characterized by reception of an input stream, input processing/output generation, and delivery of an output stream. An example of such a process is an ingress (or egress) call processing thread where data is received at one call context termination and processed according to the desired operation. Newly generated output data is delivered out of the opposite termination to the peer communication node.
When a single processing engine is tasked with handling multiple processes, the scheduler needs to ensure appropriate allocation of processing resources to each process. Two scheduling approaches are commonly used in the industry. The first approach, referred to herein as the static approach, assumes static scheduling with a fixed activation schedule for a fixed number of processes with a fixed amount of processing resources required by each process. The second approach, referred to herein as the on-demand approach, uses input packet arrival as a trigger for process scheduling
In the first approach, the scheduling mechanism makes available a predefined amount of resources to each one of a predefined number of processes. Processing resources are allocated to the processes according to a predetermined pattern, typically in a round-robin manner. For example, consider a digital signal processing (DSP) engine of a media gateway that is designed to support a maximum of two call contexts. Assuming the maximum processing resource required by each downlink (ingress) and uplink (egress) processes is 5 ms each, the scheduler invokes context-0 uplink, context-0 downlink, context-1 uplink, context-1 downlink at time instants 0 ms, 5 ms, 10 ms, and 15 ms, respectively, within each 20 ms processing period.
In the second approach, processing resources are allocated on-demand when input packets are received. For example, a bearer-relay task for a call context is activated whenever an input packet is received from an IP network. In another example, a low-bit-rate encoding task for a call context is invoked when the Pulse Code Modulation (PCM) input buffer is filled with samples received from the Public Switched Telephone Network (PSTN) network.
There are several drawbacks associated with the aforementioned scheduling mechanisms. One drawback of the static scheduling approach is in queuing delay performance, which is measured as the time difference between the actual and the desired activation times. The static design assigns an activation time to each new process without taking into account the optimal activation requirement of the process. In statistical terms, the queuing delay would have a random value, typically with a uniform distribution with respect to the desired activation times. Optimal queuing delay is not necessarily provided even when there is only one active process in the shared processing engine. In addition, the static scheduling approach is not well suited for scenarios where the configuration and processing requirements are not homogeneous. In absence of intelligent and dynamic scheduling update, queuing delay is typically higher for the static scheduling approach than it needs to be.
The on-demand approach is by nature for individual processing activation with little regard to inter-process scheduling impact. This scheduling approach is sensitive to jitter in individual activation conditions, individual resource requirement variations, and number of processes to support. In a real time multi-processing system, such as a media gateway implementation, this scheduling approach typically results in unpredictable (and often undesirable) jitter in packet output delivery.